Many theoretical and practical problems can be formulated as a general constrained nonlinear optimization problem of the following form:
                                          min                                              f              ⁡                              (                x                )                                                                                        s              .              t                                                                                                                h                    i                                    ⁡                                      (                    x                    )                                                  =                0                            ,                                                i                  ∈                  ℰ                                =                                  {                                      1                    ,                    …                    ⁢                                                                                  ,                                          n                      ℰ                                                        }                                                                                                                                                                                                                        g                    j                                    ⁡                                      (                    x                    )                                                  ≤                0                            ,                                                j                  ∈                  𝒥                                =                                  {                                      1                    ,                    …                    ⁢                                                                                  ,                                          n                      𝒥                                                        }                                                                                                                                                                  x              ∈                              R                n                                                                        (        1.1        )            where the objective function f(x), the nonlinear equality constraints hi(x), i∈ε={1, . . . , nε} and the nonlinear inequality constraints gj(x), j∈J={1, . . . , nJ} are all twice differentiable; that is, they all belong to C2:Rn→R. It is noted that maximization problems are also readily covered by (1.1) sincemax f(x)is equivalent tomin −f(x).Therefore, without loss of generality, only minimization will be considered in the following description of the optimization problems. Because of the nonlinearity and nonconvexity of the objective and constraint functions, a real world problem usually contains many local optimal solutions. Thus, obtaining a global optimal solution to (1.1) is of primary importance in real applications. Complexity of the problem (1.1) will be dramatically increased if a part or all of the optimization variables x are restricted to take a value from an associated set of discrete values which are usually integer values. These optimization problems can be formulated as a mixed integer nonlinear programming (MINLP) problem of the following form:
                                          min                                              f              ⁡                              (                                  x                  ,                  y                                )                                                                                        s              .              t                                                                                                                h                    i                                    ⁡                                      (                                          x                      ,                      y                                        )                                                  =                0                            ,                                                i                  ∈                  ℰ                                =                                  {                                      1                    ,                    …                    ⁢                                                                                  ,                                          n                      ℰ                                                        }                                                                                                                                                                                                                        g                    j                                    ⁡                                      (                                          x                      ,                      y                                        )                                                  ≤                0                            ,                                                j                  ∈                  𝒥                                =                                  {                                      1                    ,                    …                    ⁢                                                                                  ,                                          n                      𝒥                                                        }                                                                                                                                                                                  x                ∈                                  R                  n                                            ,                              y                ∈                                  Z                  m                                                                                        (        1.2        )            
MINLP has found a variety of important applications in science and engineering, including the electrical and biological engineering and the operations-research (OR) practice. For instance, the telecommunication network design and optimization, DNA data compression, traveling-salesman problems, resource allocation and constraint satisfaction problems, network reconfiguration in power grids and service restoration in distribution systems can all be formulated as MINLPs. However, even for linear objective and constraint functions in (1.2), the number of local optimal solutions to the optimization problem (1.2) usually grows exponentially as the number of integral variables y increases. As a result, the existence of multiple local optimal solutions, the number of which is typically unknown, to the optimization problem (1.2) is not only due to the nonlinearity and nonconvexity of the objective and constraint functions, but also due to the integral restriction over the variables y. Combined effects of these properties render solving the MINLP problem (1.2) a very difficult task and it is very challenging to find the global optimal solution to the MINLP problem (1.2). Indeed, many MINLP problems are classified as NP-hard problems.
There has been a wealth of research efforts focused on developing effective and robust methods to solve the MINLP problem (1.2). These methods include numerous deterministic schemes and intelligent techniques which have been brought forward in the past decades. In 1960 a general algorithm Branch-and-Bound (B&B) was proposed by A. H. Land and A. G. Doig for discrete optimization. Later on a more powerful hybrid method Branch-and-Cut (B&C) was proposed in the 1990's, which incorporated the cutting-plane method with B&B. In comparison with B&B, the method B&C usually returns high quality solutions with less time-consumption. This is mainly because the cutting plane component shortens the process to obtain an integer solution, and in turn a larger number of sub-problems can be discarded as fruitless candidates in an earlier stage. It has been noticed that only the upper bounds are considered in conventional B&B method. In fact, properly designed lower bounds can also be involved in the search procedure, resulting a faster shrink of the search space. To this end, another variant called Branch-and-Reduce (B&R) method was proposed by M. Tawarmalani and N. V. Sahinidis, where lower bounds were computed and updated by successive convex under-approximations of a relaxed problem for the MINLP problem (1.2).
With an aim to achieve better performance of B&B, many hybrid methods have been proposed where B&B is integrated with heuristic search algorithms, such as evolutionary algorithms, particle swarm optimization, ant colony, and simulated annealing. It is worthwhile noting that the actual effects of these methods can be both positive and negative. On one hand, these methods have advantages of wide applicability, easy-parallelization and robustness in the quality of solution. On the other hand, however, these methods can still suffer from several drawbacks; in particular, the accuracy of solutions obtained within limited time cannot be predicted and a global-optimal solution is not guaranteed.